Міністерство освіти та науки України
Національний Університет “Львівська політехніка”
Інститут комп´ютерних наук та інформаційних технологій
Лабораторна робота №3
з курсу:“Теорія алгоритмів і математичні основи
представлення знань”
на тему :” Емуляція на ПЕОМ машин Тюрінга.”
Мета лабораторної роботи - емуляцiя на ПЕОМ машин Тьюрінга і конструювання програм для них.
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Для засвоєння поняття машин Тьюрінга і освоєння конструювання Т-машин необхідно в певній мірі автоматизувати тестування та відладку програм Т-машин (Т-програм).
Для цього необхідно в данній лабораторній роботі емулювати на ПЕОМ машину Тьюрінга, яка б по заданій Т-програмі Пт і входу w імітувала обчислення функції F, що задається Пт.
В основі алгоритмічної системи Тюрінга лежить поняття абстрактнго автомата - машини Тюрінга (Т-машини). В літературі наведено багато варіантів визначення Т-машини. Ми розглядатемемо найбільш поширений варіант цієї машини.
Нехай задано вхідний алфавіт Eвх 2= 0 {a1,..,an}, внутрішній алфавіт Eвн 2= 0 {b1,..,br}, і E об’єднання алфавітів Eвх і Eвн, причому перетин Eвн і Eвх є пустою множиною. E будемо називати повним алфавітом. Елементи алфавітів називаються буквами або літерами.
Через E* позначимо множину всіх слів в алфавіті E, включаючи пусте слово e, а, відповідно, через E*вх - множину всіх вхідних слів.
Довільну скінченну підмножину Q 2= 0 {q0,q1,..,qm} деякої нескінченної множини Q^ 2= 0 {..,q(-1),q0,..qm,..} будемо називати множиною міток, а її елементи - мітками.
Будемо вважати, що перетин Q і E є пустою множиною. Командю Тюрінга (Т-командою ) називається вираз вигляду
q d -> q'd'r (1)
де q і q' - мітки із Q, d і d' - літери із E, а r приймає значення одного із трьох чисел : -1,0,+1. Пара qd із (1) називається Т-міткю. Програмою Тюрінга (Т-програмою) називається довільна скінченна сукупність Пт Т-команд
U0
U1 (2)
..
Um
в якій різні команди мають різні Т-мітки. Машиною Тюрінга називається довільний набір Мт 2= 0 (Q,E,q^,#,Пт), де:
Q - множина міток;
E -об'єднання вхідного Eвх та внутрішнього Eвн алфавітів;
q^ - виділений елемент із Q, який називається початковою міткою Мт;
# - виділений елемент із Eвн;
Пт - Т-програма.
Коли команда q d -> q'd'r входить в програму Пт Т-машини Мт, тоді мітка q і Т-мітка (q d) називаються прміжковими мітками. Всі непроміжкові мітки і Т-мітки називаються кінцевими мітками Т-машини Мт.
Станом Т-машини (Т-станом) називається довільна нескінченна в обидва боки послідовність
t 2= 0 ...d(-2) d(-1) q d(0) d(1) d(2)... (4)
де d(j) (j 2= 0...-2,-1,0,1,2,...) - літери із E, а q - мітка із Q.
Для машини Мт Т-стан (4) називається :
а) початковим, коли q 2= 0 q^ ;
б) проміжковим, коли < q d(0) > - проміжкова Т-мітка;
в) кінцевим, коли < q d(0) > - кінцева Т-мітка Мт.
Множину всіх станів Т-машини Мт позначимо через Dм.
Тепер визначимо функцію переходів Fт : Dм --> Dм.Коли Т-мітка <q d(0)> - кінцева в стані (4), то Fт(t) 2= 0 t.Нехай <q d(0)> - проміжова Т-мітка стану (4). Тоді в програмі Пт знайдеться одна і тільки одна команда вигляду q d(0) -> q'd'r. Під дією ціїє команди Т-стан t переходить в стан t' 2= 0 Fт(t). Залежно від r 2= 0 +1,0,-1 значення tr 2= 0 Fт(t) приймає вигляд :
t+ 2= 0 ...d(-2) d(-1) d' q' d(1) d(2)...
t0 2= 0 ...d(-2) d(-1) q' d' d(1) d(2)... (5)
t- 2= 0 ...d(-2) q' d(-1) d' d(1) d(2)...
Із (5) випливає, що при r 2= 0 +1,0,-1 вираз "q d(0)" в стані (4),відповідно, замінюється на вирази " d' q' ", "q' d' " i " q' d(-1) d' " .
Тепер опишемо, яким чином кожній Т-машині Мт можна співставити функцію f[Мт] : E*вх --> E*.Далі через /d/ 2= 0 ...ddddd... будемо позначати нескінченну послідовність літери ...
